This invention relates to a memory device for high performance real-time graphics systems for displaying flat-shaded polygons, typically used for, but not limited to, the display of 3D graphics. In a 3D system, objects are composed of polygons defined in three dimensions. The vertices of the polygons are transformed (which may include translation, rotation, and another translation) and an illumination vector may be used to determine the brightness and visibility of each polygon; each polygon is then projected and scaled for the display. The result is a list of two dimensional polygons. Each polygon is broken down into a series of horizontal lines having the appropriate Start and End addresses. A bit-mapped frame buffer is filled by writing the color data between the Start and End addresses. These techniques are well known to those skilled in the art.
A high performance real-time graphics system requires being able to write a large number of pixels in a short amount of time. This is done through a combination of writing many pixels in parallel in a memory with a short access time. However, as memories get larger a system requires fewer of them so there are fewer that can be written in parallel.
As an example, when memories were relatively small, say 64K.times.1, a 1024.times.768.times.8 frame buffer would have required 96 memories. By organizing them as 12 groups of eight memories each they could be interleaved so that with the appropriate circuitry up to 12 pixels could be written in a single memory cycle.
With larger memories now available as 256K.times.8, a 1024.times.768.times.8 frame buffer would require 3 memories; However, only one pixel can be written at a time.
Although the new memories are faster (60 ns for the new versus 150 ns for the old) it is not enough to make up for the loss of parallelism.
Currently, a high performance frame buffer would be 1024.times.768.times.24 which would require nine 256K.times.8 memories. Again, only one pixel could be written at a time.
Conventional dynamic video RAMs combine a memory array with a shift register so that an entire line of video can be transfered to the shift register in one operation so that the video can be shifted out to the video display while leaving the memory array free to accept new data. A video RAM with a shift register does not increase the number of pixels that can be written in parallel.
The 1985 patent to Rao (U.S. Pat. No. 4,498,155) shows a dynamic memory array with a shift register that allows for parallel transfers of data between the shift register and the selected memory row. Once loaded from the memory the data in the shift register can be read out independently of the memory array.
The 1985 patent to Bruce (U.S. Pat. No. 4,546,451) sets forth a dynamic RAM which permits "page mode" addressing.
The 1987 patent to Heilveil et al. (U.S. Pat. No. 4,639,890) shows a dual port video memory with selectable cascaded serial shift registers.
The 1987 patent to Kawashima (U.S. Pat. No. 4,644,502) shows a memory device in which data can be read out and/or written-in serially and at a high speed by supplying serial access clock signals thereto, and in which a CPU and the like can achieve random access to any address at a timing independent from that of the serial readout and/or write-in operation.
The 1987 patent to Voss (U.S. Pat. No. 4,646,270) sets forth a video graphic dynamic RAM having the capability of serially reading out data at a high rate of speed while performing standard RAM operations.
The 1987 patent to Pinkham et al. (U.S. Pat. No. 4,648,077) shows a dual port video memory with random and serial access ports where control functions are shared in order to minimize the number of pins.
The 1987 patent to Novak et al. (U.S. Pat. No. 4,663,735) shows a A dual port video memory with random and serial access ports where control functions are shared in order to minimize the number of pins.
The 1987 patent to Novak et al. (U.S. Pat. No. 4,688,197) sets forth a video computer system having a RAM chip with a shift register connected to its serial output terminal which is actuated by a first clock and a second clock is utilized to load the serial chip register.
The 1987 patent to Redwine et al. (U.S. Pat. No. 4,689,741) pertains to the same invention as U.S. Pat. No. 4,688,197 but provides for coupling of data between column lines and the chip register to prevent two or more different data bits from simultaneously appearing.
The 1988 patent to Gray et al. (U.S. Pat. No. 4,719,601) shows a dual port video memory with column redundancy for defective columns.
The 1988 patent to Heilveil et al. (U.S. Pat. No. 4,747,081) shows a A dual port video memory using the column address to select the serial shift register tap.
The 1988 patent to Willis (U.S. Pat. No. 4,789,960) shows a dual port memory having semi-synchronous data input and data output.
The 1989 patent to Chang (U.S. Pat. No. 4,817,051) shows a bipolar RAM with separate read and write ports that can be expanded to allow for multiple ports.
The 1989 patent to Christopher et al. (U.S. Pat. No. 4,821,226) shows a dual port video memory having a bit-serial address input port.
The 1989 patent to Hamano (U.S. Pat. No. 4,825,411) shows a dual port memory with two serial access memories.
The 1989 patent to Greub (U.S. Pat. No. 4,833,649) shows a dual port memory that permits two data processing devices to read or write data stored therein at the same time.
The 1989 patent to Yamaguchi et al. (U.S. Pat. No. 4,858,190) shows a dual port video memory with random and serial access ports.
The 1989 patent to Pinkham et al. (U.S. Pat. No. 4,866,678) shows a dual port memory having a pipelined serial output.
The 1989 patent to Nakada (U.S. Pat. No. 4,870,621) shows a dual port video memory with random and serial access ports where the serial read operation can be started from an arbitrary bit location.
The 1990 patent to Hush et al. (U.S. Pat. No. 4,891,794) shows a three port memory having a random access port and two serial ports.
The 1990 patent to Gelsomini et al. (U.S. Pat. No. 4,893,280) shows a dual port video memory with random and serial access ports where the organization of the memory bits can be controlled by the user.
The 1990 patent to Redwine et al. (U.S. Pat. No. 4,897,818) shows a dual port memory with inhibited random access during transfer cycles.
The 1991 patent to Hiltebeitel et al. (U.S. Pat. No. 4,984,214) shows a dual port memory with improved serial shift register latches.
The 1991 patent to Miyauchi et al. (U.S. Pat. No. 4,987,559) shows a multiple port video memory with a random access port and two serial access ports to allow serial read and write operations to be performed simultaneously.
The 1991 patent to Ebbers et al. (U.S. Pat. No. 5,001,672) shows a video RAM where the portion of the serial access memory to be scanned can be externally selected.
The 1991 patent to Herbert (U.S. Pat. No. 5,023,838) shows a RAM device capable of performing logic combinations of new and previously stored data in a single memory access cycle. Logic operations are performed by cell or bit.
The 1991 patent to Foss (U.S. Pat. No. 5,042,012) shows a method for serially accessing single or,dual port video RAMs by interconnecting and shifting data signals between the existing sense and restore amplifiers of the RAMs according to a master/slave action for serially shifting data out from the RAM.
The 1991 patent to Sato (U.S. Pat. No. 5,042,013) shows a dual port video memory with random and serial access ports with improved sense amplifiers and write amplifiers.
The 1991 patent to Pinkham et al. (U.S. Pat. No. 5,042,014) shows a pipeline architecture for the serial side of a dual-port memory in order to improve the speed of the speed of the serial output.
The 1991 patent to Gupta et al. (U.S. Pat. No. 5,065,368) shows a dual port video memory that facilitates the selecting from two alternate frame buffers on a per pixel basis.
The 1992 patent to Ebbers (U.S. Pat. No. 5,119,477) shows a video random access memory having a random array and serial buffer employed to speed the replication of structure state information used in the processing of hierarchical graphic data structures.
The 1992 patent to West et al. (U.S. Pat. No. 5,121,360) shows a dual port video memory with random and serial access ports where selected parts of two different rows in a random access memory are transferred simultaneously to the serial access memory via addressable transfer gates under the control of address/control log for the purpose of avoiding mid-line reloads.
The 1992 patent to Harlin et al. (U.S. Pat. No. 5,142,637) shows a dual port video memory with random and serial access ports where the random access port has two modes of access: an image access to a 16 by 1 word (which is a standard parallel data access) and a vector access which allows horizontal or vertical lines to be written within a selected 32 by 32 bit block. The data lines carry start and stop addresses that set Write masks that locate the vector within the 32 by 32 bit block. In the vector mode of operation up to 32 pixel elements stored in memory can be changed in one operation. Vectors that are larger than can fit in a 32 by 32 bit block require additional drawing cycles.
The second 1992 patent to Harlin et al. (U.S. Pat. No. 5,148,523) pertains to the same invention as U.S. Pat. No. 5,142,637.
The third 1992 patent to Harlin et al. (U.S. Pat. No. 5,148,524) pertains to the same invention as U.S. Pat. No. 5,142,637.
The 1992 patent to Sanger (U.S. Pat. No. 5,157,775) shows a dual port, dual speed image memory interface capable of controllably inputting or outputting medium speed data through a medium speed port at the same time that high speed imagery is being supplied to or read from a high speed data rate port.
The 1992 patent to Heilveil et al. (U.S. Pat. No. 5,163,024) shows a dual port video memory with random and serial access ports where the serial shift register has taps at a plurality of different locations to adapt the system to CRT screens having different resolutions.
The 1992 patent to Ishii (U.S. Pat. No. 5,170,157) shows a dual port video memory with random and serial access ports where the data is divided into two sections in such a way that row data from memory section 1 can be loaded into shift register section 1 while shift register section 2 is displaying data. Similarly, row data from memory section 2 can be loaded into shift register section 2 while shift register section 1 is displaying data. The handoff between shift register sections is seamless. Shifting data into the shift register and reading it into the memory works similarly.
The 1993 patent to West et al. (U.S. Pat. No. 5,179,372) shows a dual port video memory with random and serial access ports where selected parts of two different rows in a random access memory are transferred simultaneously to the serial access memory via addressable transfer gates under the control of address/control log for the purpose of avoiding mid-line reloads. This pertains to the same invention as U.S. Pat. No. 5,121,360.
The 1993 patent to Pinkham et al. (U.S. Pat. No. 5,195,056) shows a dual port video memory with random and serial access ports where a color register is used in conjunction with a bit mask and block write capability to increase the number of words that can be written simultaneously, typically a maximum of four.
The 1993 patent to Mori (U.S. Pat. No. 5,198,804) shows a dual port video memory with random and serial access ports where the random access memory is wider than the data input terminal; the example given is for a random access memory that is 32 bits wide with a data input terminal that is 16 bits wide. In one operating mode, called image mode, the user supplies the row address, the column address, the upper 16 bits of data, and the lower 16 bits of data. In another operating mode, called vector mode, the user supplies the row address, the column address, and a 16 bit data word that contains the starting and ending bit positions of a 32 bit data mask. The number of pixels that can be written in one operation depends on how many bits are allocated to each pixel and is not specified in the disclosure. However, the maximum number of pixels that can be written in one operation would be 32 if there is only one bit per pixel. If there were eight bits per pixel then only four pixels could be written in one operation.
The 1993 patent to Kohiyama et al. (U.S. Pat. No. 5,201,037) shows a dual port video memory with random and serial access ports where access to the random access port is disabled during transfers from the random access memory to the shift register memory.
The 1993 patent to Redwine et al. (U.S. Pat. No. 5,210,639) pertains to the same invention as U.S. Pat. No. 4,689,741.
There is no disclosure in any of the above patents of circuitry to perform massively parallel modification of data in a selected row. The present invention overcomes this limitation by moving the line drawing process into the memory device and by performing all of the pixel writing operations for a given line segment simultaneously where the line segment may be as long as the entire width of the display screen.